package core;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Stores data about Vertex, or node, objects and allows that data to be retrieved 
 * in constant time.  It also stores useful subsets of the nodes that may be relevant.
 * @author Michael Pitts
 *
 */
public class PrePushData  {
	
	/** Maps each Vertex to its data.*/
	private final Map<Vertex, NodeData> my_map;
	
	/** Stores the flow over each Edge.*/
	private final Map<Edge, Double> my_flow;
	
	/** Stores the set of Vertex objects that have a positive excess.*/
	protected final Set<Vertex> my_overflow_nodes;
	
	/** The total flow going into the sink.*/
	private int my_total;
	
	/** The set of edges adjacent, or going into, the sink.*/
	private final Set<Edge> my_sink_edges = new HashSet<Edge>();
	
	/** The sink Vertex, or node, for the underlying graph.*/
	private Vertex my_sink;
	
	/** The source Vertex, or node, for the underlying graph.*/
	private Vertex my_source;
	
	/**
	 * Creates a new PrePushData object, which will store the needed data for 
	 * running the pre flow push algorithm on a SimpleGraph.
	 * @param the_graph is the SimpleGraph the algorithm will run on.
	 * @param the_overflow_set is the data structure that will be used to store 
	 * nodes with overflow.
	 */
	protected PrePushData(final SimpleGraph the_graph, 
			final Set<Vertex> the_overflow_set) {
		my_overflow_nodes= the_overflow_set;
		final int adjusted_size = Math.round(1.34f*the_graph.vertexList.size()) + 1;
		my_map = new HashMap<Vertex, NodeData>(adjusted_size);
		setUpNodeMap(the_graph);
		final int size = Math.round(the_graph.edgeList.size()*1.34f) + 1;
		my_flow = new HashMap<Edge, Double>(size);
		setUpFlow(the_graph);
	}
	
	/**
	 * Creates a new PrePushData object, which will store the needed data for 
	 * running the pre flow push algorithm on a SimpleGraph.  This instance will
	 * not favor nodes by height in any way.
	 * @param the_graph is the SimpleGraph the algorithm will run on.
	 */
	public PrePushData(final SimpleGraph the_graph) {
		this(the_graph, new HashSet<Vertex>());
		}
	
	/**
	 * Sets up the Map that will store Vertex, or node, data.
	 * @param the_graph is the simple graph that stores the nodes.
	 */
	@SuppressWarnings("unchecked")
	private void setUpNodeMap(final SimpleGraph the_graph) {
		for (Vertex v : (List<Vertex>)(the_graph.vertexList)) {
			my_map.put(v, new NodeData());
			if ("s".compareToIgnoreCase((String) v.getName()) == 0) {
				my_source = v;
				setHeight(my_source, the_graph.vertexList.size());
			} else if ("t".compareToIgnoreCase((String) v.getName()) == 0) {
				my_sink = v;
			}
		}
	}

	/**
	 * Sets up the Map that will store the flow for each Edge in the graph.
	 * @param the_graph is the SimpleGraph that the Edges will be pulled from.
	 */
	@SuppressWarnings("unchecked")
	private void setUpFlow(final SimpleGraph the_graph) {
		for (Edge e : (List<Edge>)(the_graph.edgeList)) {
			if (my_sink.equals(e.getSecondEndpoint())) {
				put(e, 0.0);
				my_sink_edges.add(e); // get all sink edges
			}
			if (my_source.equals(e.getFirstEndpoint())) {
				put(e, (Double) e.getData()); // initialize all source edges to max
				setExcess(e.getSecondEndpoint(), (Double) e.getData());
				changeExcess(my_source, -(Double) e.getData());
			} else put(e, 0.0); // neither source nor sink edge, starts with 0 flow
		}
	}

	/**
	 * Adds a new node into the NodeMap or overwrites the existing data.
	 * @param key is the new node.
	 * @param value is the new NodeData object.
	 * @return the old data if overwritten.
	 * @see Map#put(Object, Object)
	 */
	protected NodeData put(final Vertex key, final NodeData value) {
		if (value.excess > 0 && !my_sink.equals(key)) my_overflow_nodes.add(key);
		else my_overflow_nodes.remove(key);
		return my_map.put(key, value);
	}
	
	/**
	 * Gets the next node that has an overflow.
	 * @throws NoSuchElementException if there are no more nodes with excess.
	 */
	public Vertex getExcessNode() {return my_overflow_nodes.iterator().next();}
	
	/**
	 * Tells you if there are any more nodes with excess left.
	 * @return true if there is at least one more node with excess left, 
	 * false otherwise.
	 */
	public boolean hasExcessNodes() {return my_overflow_nodes.size() > 0;}
	
	/**
	 * Sets the excess for a given node.
	 * @param key is the node, or Vertex, who's excess is to change.
	 * @param the_excess is the new excess value.
	 */
	private void setExcess(final Vertex key, final double the_excess) {
		final NodeData value = my_map.get(key);
		value.excess = the_excess;
		put(key, value);
	}

	/** Gets the height of the specified Vertex.*/
	public int getHeight(final Vertex the_key) {
		return my_map.get(the_key).height;
	}

	/** Increases the height of the specified Vertex by one.*/
	public int increaseHeight(final Vertex the_key) {
		final NodeData data = my_map.get(the_key);
		data.height++;
		return data.height;
	}

	/** Gets the excess of the given Vertex.*/
	public double getExcess(final Vertex the_key) {
		return my_map.get(the_key).excess;
	}

	/** 
	 * Changes the excess of a particular Vertex by the amount given.
	 * @param the_key is the Vertex to have its excess changed.
	 * @param excess_change is the amount by which to change the excess.
	 */
	public void changeExcess(final Vertex the_key, final double excess_change) {
		final double original = my_map.get(the_key).excess;
		setExcess(the_key, excess_change + original);
	}

	/**
	 * Sets the height of a given Vertex.
	 * @param the_key is the Vertex who's height is to change.
	 * @param the_height is the new height for the given vertex.
	 */
	private void setHeight(final Vertex the_key, final int the_height) {
		my_map.get(the_key).height = the_height;
	}
	
	/**
	 * Maps a particular Edge to a given flow value.
	 * @param key is the Edge who will have a new or overwritten flow value.
	 * @param value is the new flow value for the given edge.
	 * @return the old flow value, if it is overwritten.
	 * @see Map#put(Object, Object)
	 */
	private final Double put(final Edge key, final Double value) {
		if (my_sink_edges.contains(key)) my_total += value - my_flow.get(key);
		return my_flow.put(key, value);
	}

	/** Gets the total flow into the sink, over all Edges.*/
	public int getNetFlow() {return my_total;}

	/**
	 * Changes the flow value for a given Edge.
	 * @param the_edge is the Edge to change.
	 * @param delta is the amount by which to change the flow.
	 */
	public void change(final Edge the_edge, final double delta) {
		final double old = my_flow.get(the_edge);
		put(the_edge, old + delta);
	}

	/** Gets the flow value for a given Edge.*/
	public double get(final Edge the_edge) {
		return my_flow.get(the_edge);
	}

	/**
	 * Returns true if there are more edges to consider for the given vertex and the
	 * given vertex has excess flow.
	 * @param the_node is the Vertex to consider.
	 * @return true if the_node has more edges to examine and still has excess flow, 
	 * false otherwise.
	 * @see PrePushData#nextEdge
	 * @see PrePushData#resetEdge
	 */
	public boolean hasNextEdgeAndExcess(final Vertex the_node) {
		return (my_map.get(the_node).next < the_node.incidentEdgeList.size()) &&
				my_map.get(the_node).excess > 0;
	}
	
	/** Gets the next Edge to examine for the given node.*/
	public Edge nextEdge(final Vertex the_node) {
		final Edge edge = 
				(Edge) the_node.incidentEdgeList.get(my_map.get(the_node).next);
		my_map.get(the_node).next = my_map.get(the_node).next + 1;
		return edge;
	}
	
	/** Resets the given node's next edge back to the beginning.*/
	public void resetEdge(final Vertex the_node) {
		my_map.get(the_node).next = 0;
	}
	
	/** Stores the data about any given Vertex, or node.*/
	protected class NodeData {
		/** The excess flow at the given node.*/
		public double excess = 0;
		
		/** The height of the given node.*/
		public int height = 0;
		
		/** The next Edge in the given nodes's edge list to examine.*/
		public int next = 0;
	}
}
